1841C - Ranom Numbers - CodeForces Solution

#include <bits/stdc++.h>
#include <unordered_map>
#define int long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back

using namespace std;
int md = 1e9+7 ;

int power(int x, int y){
	if(y==0){
		return 1; 
	}
	
	if(y==1){
		return x ;
	}
	int ans = power(x,y/2) ;
	ans*=ans;
	ans%=md ;
	
	if(y%2==1){
		ans*=x; 
		ans%=md ;
	}
	return ans ;
}


int32_t main(){
 
 
 ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
//	freopen("input.txt","r",stdin) ;
//	freopen("output.txt","w",stdout) ;

 int tt =1 ;
 cin>>tt ;



for(int ii=0 ; ii<tt ; ii++ ){
	int n;
	string s ;
	cin>>s ;
		n = s.length() ;
		
		if(n==1){
			cout<<10000<<endl ;
			continue; 
		}
		
	vector<int>a(n,0) ;
	
	f(j,0,n){
		a[j] = s[j] - 'A' ;
	}
	

	
	vector<vector<int>>dp(n,vector<int>(5,0)) ;
	vector<int>mx(n,0) ;
	vector<int>val(n+1,0) ;
	
	int ans = -1e9 ;
	
	fd(j,n-1,0){
		if(j<n-1)
		mx[j] = max(a[j],mx[j+1]) ; 
		else
		mx[j] = a[j] ;
		
		if(a[j] < mx[j] ){
			val[j] = val[j+1] - power(10,a[j]) ;
		}
		else{
			val[j] = val[j+1] + power(10,a[j]) ;
		}
	//	cout<<mx[j]<<endl ;
	}
	
	f(j,0,5){
		
		if( a[0] >= j  ){
			dp[0][j] = power(10,a[0]) ; 
		}
		else{
			dp[0][j] = -power(10,a[0]) ;
		}
	}
	
	f(j,1,n){
		
		f(i,0,5){
			int k = max(i,a[j]) ;
			if(a[j] >= i )
			dp[j][i] = dp[j-1][k] + power(10,a[j]) ;
			else
			dp[j][i] = dp[j-1][k] - power(10,a[j]) ;
		//	cout<<dp[j][i]<<" " ;
		}
		
	//	cout<<endl ;
	}
	
	fd(j,n-1,0){
		
		if(j==n-1){
			
			f(i,0,5){
				int k = power(10,i) ;
				ans = max(ans,dp[j-1][i] + k ) ;
			}
			
			
		}
		else{
			
			int allowed = mx[j+1] ;
			
			f(i,allowed,5){
				int k = power(10,i) ;
			//	cout<<k<<endl ;
				int mm = 0 ;
				
				if(j>0){
					mm = dp[j-1][i] ;
				}
				ans = max(ans,mm + k+ val[j+1] ) ;
			}
			
			
		}
		
	}
	
	cout<<ans<<endl ;
	
}
	
	

return 0;
 
}